/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BASB30/FONT#2=ASI30[LSP,JRA]/FONT#3=SUB/FONT#4=ASI30[LSP,JRA]/FONT#5=BASB30/FONT#6=GRK30/FONT#7=SUP/FONT#8=SPEC[LSP,JRA]/FONT#9=SET1/FONT#10=GRFX25[LSP,JRA]/FONT#11=FIX30/FONT#12=NGB30/FONT#13=GERM35/FONT#14=MG[LSP,JRA]/FONT#15=GRFX35



␈↓ ↓H␈↓␈↓ ∧1␈↓↓PREFACE␈↓


␈↓ ↓H␈↓␈↓ ∧λ"...␈αit␈αis␈αimportant␈α
not␈αto␈αlose␈αsight␈α
of␈αthe
␈↓ ↓H␈↓␈↓ ∧λfact␈α∪that␈α∪there␈α∪is␈α∪a␈α∀difference␈α∪between
␈↓ ↓H␈↓␈↓ ∧λtraining␈α≤and␈α≤education.␈α≤ If␈α≠computer
␈↓ ↓H␈↓␈↓ ∧λscience␈α∂is␈α∂a␈α∂fundamental␈α∂discipline,␈α∞then
␈↓ ↓H␈↓␈↓ ∧λuniversity␈α∂education␈α∂in␈α∂this␈α∂field␈α∂should
␈↓ ↓H␈↓␈↓ ∧λemphasize␈α?␈αβenduring␈α?␈ααfundamental
␈↓ ↓H␈↓␈↓ ∧λprinciples␈α∪rather␈α∪than␈α∀transient␈α∪current
␈↓ ↓H␈↓␈↓ ∧λtechnology."

␈↓ ↓H␈↓␈↓ β-Peter Wegner, ␈↓αThree Computer Cultures␈↓[Weg 70] 

␈↓ ↓H␈↓This␈αtext␈α
is␈αnominally␈αabout␈α
LISP␈αand␈αdata␈α
structures.␈αHowever,
␈↓ ↓H␈↓in␈α
the␈α
process␈α∞it␈α
covers␈α
much␈α∞broader␈α
areas␈α
of␈α∞computer␈α
science.
␈↓ ↓H␈↓The␈α
author␈αhas␈α
long␈α
felt␈αthat␈α
the␈αbeginning␈α
student␈α
of␈αcomputer
␈↓ ↓H␈↓science␈α
has␈α
been␈αgetting␈α
a␈α
distorted␈αand␈α
disjointed␈α
picture␈α
of␈αthe
␈↓ ↓H␈↓field.␈α∞In␈α∞some␈α∞ways␈α∞this␈α∂confusion␈α∞is␈α∞natural;␈α∞the␈α∞field␈α∂has␈α∞been
␈↓ ↓H␈↓growing␈αat␈α
such␈αa␈αrapid␈α
rate␈αthat␈αfew␈α
are␈αprepared␈αto␈α
be␈αjudged
␈↓ ↓H␈↓experts␈α∩in␈α∩all␈α∩areas␈α∩of␈α∩the␈α∩discipline.␈α∩ The␈α∩current␈α∩alternative
␈↓ ↓H␈↓seems␈α∂to␈α∂be␈α∂to␈α∂give␈α∂a␈α∂few␈α∂introductory␈α∂courses␈α∂in␈α∂programming
␈↓ ↓H␈↓and␈α→machine␈α~organization␈α→followed␈α→by␈α~relatively␈α→specialized
␈↓ ↓H␈↓courses␈αin␈αmore␈αtechnical␈αareas.␈αThe␈αdifficulty␈αwith␈αthis␈αapproach
␈↓ ↓H␈↓is␈α⊃that␈α⊃much␈α⊃of␈α⊃the␈α⊃technical␈α⊃material␈α⊃never␈α⊃gets␈α∩related.␈α⊃The
␈↓ ↓H␈↓student's␈α∞perspective␈α∞and␈α∞motivation␈α∞suffers␈α∞in␈α∞the␈α∂process.␈α∞This
␈↓ ↓H␈↓book␈αuses␈αLISP␈αas␈αa␈αmeans␈αfor␈αrelating␈αtopics␈αwhich␈αnormally␈αget
␈↓ ↓H␈↓treated␈α
in␈α
several␈α
separate␈α
courses.␈α∞The␈α
point␈α
is␈α
not␈α
that␈α∞we␈α
␈↓↓can␈↓
␈↓ ↓H␈↓do␈α∂this␈α∞in␈α∂LISP,␈α∞but␈α∂rather␈α∞that␈α∂it␈α∞is␈α∂␈↓↓natural␈↓␈α∞to␈α∂do␈α∞it␈α∂in␈α∞LISP.
␈↓ ↓H␈↓The␈αhigh-level␈αnotation␈αfor␈αalgorithms␈αis␈αbeneficial␈αin␈αexplaining
␈↓ ↓H␈↓and␈αunderstanding␈αcomplex␈αalgorithms.␈α The␈αuse␈αof␈αabstract␈αdata
␈↓ ↓H␈↓structures␈α↔and␈α_abstract␈α↔LISP␈α↔programs␈α_shows␈α↔the␈α_intent␈α↔of
␈↓ ↓H␈↓structured␈α⊂programming␈α⊂and␈α⊂step-wise␈α⊂refinement.␈α⊂Much␈α⊂of␈α⊂the
␈↓ ↓H␈↓current␈αwork␈αin␈αmathematical␈αtheories␈αof␈αcomputation␈αis␈αbased␈αon
␈↓ ↓H␈↓LISP-like␈α⊃languages.␈α⊃Thus␈α∩LISP␈α⊃is␈α⊃a␈α⊃formalism␈α∩for␈α⊃describing
␈↓ ↓H␈↓algorithms,␈α∂for␈α∂writing␈α⊂programs,␈α∂and␈α∂for␈α∂proving␈α⊂properties␈α∂of
␈↓ ↓H␈↓algorithms.␈α⊂ We␈α⊂use␈α⊃data␈α⊂structures␈α⊂as␈α⊃the␈α⊂main␈α⊂thread␈α⊃in␈α⊂our
␈↓ ↓H␈↓discussions␈α⊃because␈α⊃a␈α⊃proper␈α⊂appreciation␈α⊃of␈α⊃data␈α⊃structures␈α⊂as
␈↓ ↓H␈↓abstract␈αobjects␈αis␈αa␈αnecessary␈αprerequisite␈αto␈αan␈αunderstanding␈αof
␈↓ ↓H␈↓modern computer science.

␈↓ ↓H␈↓The␈α
importance␈αof␈α
abstraction␈α
obviously␈αgoes␈α
much␈α
further␈αthan
␈↓ ↓H␈↓its␈αappearance␈αin␈αLISP.␈αAbstraction␈αhas␈αoften␈αbeen␈αused␈αin␈αother



␈↓ ↓H␈↓disciplines␈αas␈αa␈α
means␈αfor␈αcontrolling␈αcomplexity.␈α
In␈αmathematics,
␈↓ ↓H␈↓we␈α⊗frequently␈α⊗are␈α∃able␈α⊗to␈α⊗gain␈α∃new␈α⊗insights␈α⊗by␈α⊗recasting␈α∃a
␈↓ ↓H␈↓particularly␈α_intransigent␈α_problem␈α→in␈α_a␈α_more␈α→general␈α_setting.
␈↓ ↓H␈↓Similarly,␈α⊃the␈α⊃intent␈α⊃of␈α⊃an␈α⊃algorithm␈α⊃expressed␈α⊃in␈α⊃a␈α⊂high-level
␈↓ ↓H␈↓language␈α∞like␈α∞Fortran␈α∞or␈α∞PL/1␈α
is␈α∞more␈α∞readily␈α∞apparent␈α∞than␈α
its
␈↓ ↓H␈↓machine-language␈α⊃equivalent.␈α⊃ These␈α⊃are␈α⊃both␈α⊃examples␈α∩of␈α⊃the
␈↓ ↓H␈↓use␈α∂of␈α∞abstraction.␈α∂Our␈α∂use␈α∞of␈α∂abstraction␈α∞will␈α∂impinge␈α∂on␈α∞both
␈↓ ↓H␈↓the␈αmathematical␈α
and␈αthe␈αprogramming␈α
aspects.␈α Initially,␈α
we␈αwill
␈↓ ↓H␈↓talk␈α~about␈α~data␈α~structures␈α≠as␈α~abstract␈α~objects␈α~just␈α≠as␈α~the
␈↓ ↓H␈↓mathematician␈α
takes␈αthe␈α
natural␈α
numbers␈αas␈α
abstract␈α
entities.␈αWe
␈↓ ↓H␈↓will␈α⊃attempt␈α⊃to␈α⊃categorize␈α⊂properties␈α⊃common␈α⊃to␈α⊃data␈α⊂structures
␈↓ ↓H␈↓and␈α
introduce␈α∞notation␈α
for␈α
describing␈α∞functions␈α
defined␈α∞on␈α
these
␈↓ ↓H␈↓abstractions.␈α⊂At␈α⊂this␈α⊂level␈α⊂of␈α∂discussion␈α⊂we␈α⊂are␈α⊂thinking␈α⊂of␈α∂our
␈↓ ↓H␈↓LISP-like␈α∂language␈α∞primarily␈α∂as␈α∞a␈α∂notational␈α∂convenience␈α∞rather
␈↓ ↓H␈↓than␈αa␈αcomputational␈αdevice.␈α However,␈αafter␈αa␈αcertain␈αfamiliarity
␈↓ ↓H␈↓has␈αbeen␈αestablished␈αit␈αis␈αimportant␈αto␈αlook␈αat␈αour␈αwork␈αfrom␈αthe
␈↓ ↓H␈↓viewpoint␈α↔of␈α↔computer␈α↔science.␈α↔Here␈α↔we␈α↔must␈α↔think␈α↔of␈α⊗the
␈↓ ↓H␈↓computational␈α
aspects␈α
of␈α
our␈αnotation.␈α
We␈α
must␈α
be␈αconcerned␈α
with
␈↓ ↓H␈↓the␈α!representational␈α"problems:␈α!implementation␈α"on␈α!realistic
␈↓ ↓H␈↓machines,␈α→and␈α→efficiency␈α_of␈α→algorithms␈α→and␈α→data␈α_structures.
␈↓ ↓H␈↓However,␈α→it␈α→cannot␈α→be␈α→over-emphasized␈α→that␈α→our␈α→need␈α→for
␈↓ ↓H␈↓understanding␈α
is␈αbest␈α
served␈αat␈α
the␈α
higher␈αlevel␈α
of␈αabstraction;␈α
the
␈↓ ↓H␈↓advantage␈α∀of␈α∀a␈α∀high-level␈α∀language␈α∀is␈α∀notational␈α∀rather␈α∀than
␈↓ ↓H␈↓computational.␈α⊂That␈α⊂is,␈α⊂it␈α⊂allows␈α∂us␈α⊂to␈α⊂think␈α⊂and␈α⊂represent␈α∂our
␈↓ ↓H␈↓algorithms␈α∩in␈α∩mathematical␈α∩terms␈α∩rather␈α∩than␈α∩in␈α∩terms␈α∪of␈α∩the
␈↓ ↓H␈↓machine.␈α It␈αis␈αonly␈αafter␈αa␈αclear␈αunderstanding␈αof␈αthe␈α
problem␈αis
␈↓ ↓H␈↓attained that we should begin thinking about representation.

␈↓ ↓H␈↓We␈α⊂can␈α⊃exploit␈α⊂the␈α⊃analogy␈α⊂with␈α⊃traditional␈α⊂mathematics␈α⊃a␈α⊂bit
␈↓ ↓H␈↓further.␈α∞ When␈α∞we␈α∞write␈α∞␈↓αsqrt(x)␈↓␈α∞in␈α∞Fortran,␈α∞for␈α∞example,␈α∞we␈α∞are
␈↓ ↓H␈↓initially␈α∀only␈α∀concerned␈α∀with␈α∀␈↓αsqrt␈↓␈α∀as␈α∀a␈α∃mathematical␈α∀function
␈↓ ↓H␈↓defined␈αsuch␈αthat␈α␈↓αx = sqrt(x)*sqrt(x)␈↓.␈αWe␈αare␈αnot␈αinterested␈αin␈αthe
␈↓ ↓H␈↓specific␈α∞algorithm␈α∂used␈α∞to␈α∞approximate␈α∂the␈α∞function␈α∂intended␈α∞in
␈↓ ↓H␈↓the␈α⊃notation.␈α⊂Indeed,␈α⊃thought␈α⊂of␈α⊃as␈α⊂a␈α⊃mathematical␈α⊃notation,␈α⊂it
␈↓ ↓H␈↓doesn't␈α⊃matter␈α⊃how␈α⊂␈↓αsqrt␈↓␈α⊃is␈α⊃computed.␈α⊂We␈α⊃might␈α⊃wish␈α⊃to␈α⊂prove
␈↓ ↓H␈↓some␈α
properties␈α
of␈α
the␈α
algorithm␈α
which␈α
we␈α
are␈α
encoding.␈α
 If␈αso,␈α
we
␈↓ ↓H␈↓would␈α⊗only␈α∃use␈α⊗the␈α∃mathematical␈α⊗properties␈α∃of␈α⊗the␈α∃idealized
␈↓ ↓H␈↓square␈αroot␈αfunction.␈αOnly␈α
later,␈αafter␈αwe␈αhad␈αconvinced␈α
ourselves
␈↓ ↓H␈↓of␈α
the␈α
correct␈α∞encoding␈α
of␈α
our␈α∞intention␈α
in␈α
the␈α∞Fortran␈α
program,
␈↓ ↓H␈↓would␈α∂we␈α∞worry␈α∂about␈α∞the␈α∂computational␈α∞aspects␈α∂of␈α∂the␈α∞Fortran
␈↓ ↓H␈↓implementation␈α∂␈↓αsqrt␈↓.␈α∂The␈α∂typical␈α∂user␈α∂will␈α∂never␈α∂proceed␈α∞deeper
␈↓ ↓H␈↓into␈α∃the␈α∃representation␈α∃than␈α∃this;␈α∃only␈α∃if␈α∃his␈α∃computation␈α∃is
␈↓ ↓H␈↓lethargic␈α
due␈αto␈α
inefficiencies,␈αor␈α
inaccurate␈αdue␈α
to␈αuncooperative
␈↓ ↓H␈↓approximations, will he look at the actual implementation of ␈↓αsqrt␈↓.



␈↓ ↓H␈↓Just␈α∪as␈α∪it␈α∪is␈α∀unnecessary␈α∪to␈α∪learn␈α∪machine␈α∪language␈α∀to␈α∪study
␈↓ ↓H␈↓numerical␈α∀algorithms,␈α∀it␈α∀is␈α∀also␈α∀unnecessary␈α∀to␈α∀learn␈α∪machine
␈↓ ↓H␈↓language␈αto␈αunderstand␈αnon-numerical␈αor␈αdata␈αstructure␈αprocesses.
␈↓ ↓H␈↓We␈α↔make␈α↔a␈α↔distinction␈α⊗between␈α↔data␈α↔structures␈α↔and␈α⊗storage
␈↓ ↓H␈↓structures.␈α⊂Data␈α⊂structures␈α⊂are␈α⊂abstractions,␈α⊂independent␈α⊃of␈α⊂␈↓¬how␈↓
␈↓ ↓H␈↓they␈α~are␈α~implemented␈α≠on␈α~a␈α~machine.␈α~ Data␈α≠structures␈α~are
␈↓ ↓H␈↓representations␈α
of␈α
information␈α∞chosen␈α
to␈α
exhibit␈α∞certain␈α
ordering
␈↓ ↓H␈↓and␈α≤accessibility␈α≠relationships␈α≤between␈α≠data␈α≤items.␈α≠ Storage
␈↓ ↓H␈↓structures␈α∩are␈α∩particular␈α∪implementations␈α∩of␈α∩the␈α∪abstract␈α∩ideas.
␈↓ ↓H␈↓Certainly␈α_we␈α↔cannot␈α_ignore␈α_storage␈α↔structures␈α_when␈α_we␈α↔are
␈↓ ↓H␈↓deciding␈α≠upon␈α≤the␈α≠data␈α≠structures␈α≤which␈α≠will␈α≤encode␈α≠the
␈↓ ↓H␈↓algorithm,␈α∪but␈α∪the␈α∀interesting␈α∪aspects␈α∪of␈α∪the␈α∀representation␈α∪of
␈↓ ↓H␈↓information␈α
can␈α∞be␈α
discussed␈α∞at␈α
the␈α
level␈α∞of␈α
data␈α∞structures␈α
with
␈↓ ↓H␈↓no␈α
loss␈α
of␈α∞generality.␈α
 The␈α
mapping␈α∞of␈α
data␈α
structures␈α∞to␈α
storage
␈↓ ↓H␈↓structures␈α∂is␈α⊂usually␈α∂quite␈α∂machine␈α⊂dependent␈α∂and␈α∂we␈α⊂are␈α∂more
␈↓ ↓H␈↓interested␈α∪in␈α∩ideas␈α∪than␈α∪coding␈α∩tricks.␈α∪ We␈α∪will␈α∩see␈α∪that␈α∪it␈α∩is
␈↓ ↓H␈↓possible,␈αand␈αmost␈αbeneficial,␈αto␈αstructure␈αour␈αprograms␈α
such␈αthat
␈↓ ↓H␈↓there␈αis␈αa␈αvery␈αclean␈αinterface␈αbetween␈αthe␈αabstract␈αalgorithm␈αand
␈↓ ↓H␈↓the␈α↔chosen␈α_representation.␈α↔ That␈α_is,␈α↔there␈α↔will␈α_be␈α↔a␈α_set␈α↔of
␈↓ ↓H␈↓representation-manipulating␈α⊃programs␈α⊃to␈α⊃test,␈α⊃select␈α⊃or␈α⊂construct
␈↓ ↓H␈↓elements␈αof␈α
the␈αdomain;␈αand␈α
there␈αwill␈αbe␈α
a␈αprogram␈αencoding␈α
the
␈↓ ↓H␈↓algorithm.␈α∩To␈α∪change␈α∩representations␈α∪only␈α∩requires␈α∪changes␈α∩to
␈↓ ↓H␈↓constructors, selectors and predicates, not to the basic program.

␈↓ ↓H␈↓One␈αimportant␈αinsight␈αwhich␈αshould␈αbe␈αcultivated␈αin␈α
this␈αprocess
␈↓ ↓H␈↓is␈αthe␈αdistinction␈αbetween␈αthe␈αconcepts␈αof␈αfunction␈αand␈αalgorithm.
␈↓ ↓H␈↓The␈α
idea␈α
of␈α
function␈α∞is␈α
mathematical␈α
and␈α
is␈α
independent␈α∞of␈α
any
␈↓ ↓H␈↓notion␈α#of␈α$computation;␈α#the␈α$meaning␈α#of␈α$"algorithm"␈α#is
␈↓ ↓H␈↓computational,␈α∪the␈α∩effect␈α∪of␈α∩an␈α∪algorithm␈α∩being␈α∪to␈α∪compute␈α∩a
␈↓ ↓H␈↓function.␈α∩Thus␈α⊃there␈α∩are␈α∩typically␈α⊃many␈α∩algorithms␈α∩which␈α⊃will
␈↓ ↓H␈↓compute a specific function.

␈↓ ↓H␈↓This␈αtext␈α
is␈α␈↓↓not␈↓␈α
meant␈αto␈αbe␈α
a␈αprogramming␈α
manual␈αfor␈αLISP.␈α
 A
␈↓ ↓H␈↓certain␈αamount␈αof␈α
time␈αis␈αspent␈α
giving␈αinsights␈αinto␈αtechniques␈α
for
␈↓ ↓H␈↓writing␈αLISP␈αfunctions.␈α There␈αare␈αtwo␈αreasons␈αfor␈αthis.␈αFirst,␈αthe
␈↓ ↓H␈↓style␈α↔of␈α↔LISP␈α⊗programming␈α↔is␈α↔quite␈α⊗different␈α↔from␈α↔that␈α⊗of
␈↓ ↓H␈↓"normal"␈α∂programming.␈α∂ LISP␈α∞was␈α∂one␈α∂of␈α∞the␈α∂first␈α∂languages␈α∞to
␈↓ ↓H␈↓exploit␈α∩the␈α∪virtues␈α∩of␈α∩recursive␈α∪programming␈α∩and␈α∪explore␈α∩the
␈↓ ↓H␈↓power␈α⊃of␈α⊃procedure-valued␈α⊃variables.␈α⊃ Second,␈α⊃we␈α⊃will␈α⊃spend␈α⊃a
␈↓ ↓H␈↓great␈α
deal␈α∞of␈α
time␈α
discussing␈α∞various␈α
levels␈α
of␈α∞implementation␈α
of
␈↓ ↓H␈↓the␈α↔language.␈α↔LISP␈α↔is␈α⊗an␈α↔excellent␈α↔medium␈α↔for␈α⊗introducing
␈↓ ↓H␈↓standard␈α⊂techniques␈α∂in␈α⊂data␈α∂structure␈α⊂manipulation.␈α∂Techniques
␈↓ ↓H␈↓for␈α
implementation␈α
of␈α
recursion,␈α
implementation␈α
of␈α
complex␈αdata



␈↓ ↓H␈↓structures,␈α∩storage␈α⊃management,␈α∩and␈α⊃symbol␈α∩table␈α⊃manipulation
␈↓ ↓H␈↓are␈α∂easily␈α∂motivated␈α⊂in␈α∂the␈α∂context␈α∂of␈α⊂language␈α∂implementation.
␈↓ ↓H␈↓Many␈α!of␈α!these␈α"standard␈α!techniques␈α!first␈α!arose␈α"in␈α!the
␈↓ ↓H␈↓implementation␈αof␈α
LISP.␈αBut␈α
it␈αis␈α
pointless␈αto␈α
attempt␈αa␈α
discussion
␈↓ ↓H␈↓of␈α
implementation␈αunless␈α
the␈α
reader␈αhas␈α
a␈αthorough␈α
grasp␈α
of␈αthe
␈↓ ↓H␈↓language.

␈↓ ↓H␈↓Granting␈α∞the␈α∞efficacy␈α∞of␈α∞our␈α∞endeavor␈α∞in␈α∞abstraction,␈α∞why␈α∞study
␈↓ ↓H␈↓LISP?␈α LISP␈αis␈αat␈αleast␈αfifteen␈αyears␈αold␈αand␈αmany␈αlanguages␈αnew
␈↓ ↓H␈↓languages␈α→have␈α→been␈α→proposed.␈α→ The␈α→difficulty␈α→is␈α→that␈α→the
␈↓ ↓H␈↓appropriate␈α∂combination␈α⊂of␈α∂these␈α∂features␈α⊂is␈α∂not␈α∂present␈α⊂in␈α∂any
␈↓ ↓H␈↓other␈α∪language.␈α∪LISP␈α∪unifies␈α∪and␈α∪rationalizes␈α∀many␈α∪divergent
␈↓ ↓H␈↓formulations␈α⊂of␈α∂language␈α⊂constructs.␈α⊂ One␈α∂might␈α⊂surmise␈α⊂that␈α∂a
␈↓ ↓H␈↓new␈α⊂language,␈α⊂profiting␈α⊂from␈α⊂LISP's␈α⊂experience,␈α⊂would␈α⊂make␈α⊂a
␈↓ ↓H␈↓better␈α∩pedagogical␈α∩tool.␈α∩ Toy␈α⊃languages␈α∩are␈α∩suspect␈α∩for␈α⊃several
␈↓ ↓H␈↓reasons.␈αThe␈αstudent␈αmay␈αsuspect␈αthat␈αhe␈αis␈αa␈αsubject␈αin␈αa␈αnot␈αtoo
␈↓ ↓H␈↓clever␈α⊂experiment␈α∂being␈α⊂performed␈α⊂upon␈α∂him␈α⊂by␈α⊂his␈α∂instructor.
␈↓ ↓H␈↓Having␈α∩a␈α∩backlog␈α∩of␈α∩fifteen␈α∩years␈α∩of␈α∩experience␈α∩and␈α⊃example
␈↓ ↓H␈↓programs␈α∃should␈α⊗do␈α∃much␈α∃to␈α⊗alleviate␈α∃this␈α⊗discomfort.␈α∃ The
␈↓ ↓H␈↓development␈α∂of␈α∂LISP␈α∞also␈α∂shows␈α∂many␈α∞of␈α∂the␈α∂mistakes␈α∂that␈α∞the
␈↓ ↓H␈↓original␈αimplementors␈αand␈αdesigners␈αmade.␈α We␈αwill␈αpoint␈αout␈αthe
␈↓ ↓H␈↓flaws and pitfalls awaiting the unwary language designer.

␈↓ ↓H␈↓We␈α⊂claim␈α⊃the␈α⊂more␈α⊃interesting␈α⊂aspects␈α⊂of␈α⊃LISP␈α⊂for␈α⊃students␈α⊂of
␈↓ ↓H␈↓Computer␈α⊗Science␈α⊗lie␈α⊗not␈α⊗in␈α⊗its␈α⊗features␈α⊗as␈α↔a␈α⊗programming
␈↓ ↓H␈↓language,␈α↔but␈α⊗in␈α↔what␈α↔it␈α⊗can␈α↔show␈α⊗about␈α↔the␈α↔␈↓↓structure␈↓␈α⊗of
␈↓ ↓H␈↓Computer␈α_Science.␈α_ There␈α→is␈α_a␈α_rapidly␈α_expanding␈α→body␈α_of
␈↓ ↓H␈↓knowledge␈αunique␈αto␈αComputer␈αScience,␈αneither␈αmathematical␈αnor
␈↓ ↓H␈↓engineering␈α
per␈αse.␈α
 Much␈α
of␈αthis␈α
area␈α
is␈αpresented␈α
most␈αclearly␈α
by
␈↓ ↓H␈↓studying LISP.

␈↓ ↓H␈↓Again␈α
there␈α∞are␈α
two␈α∞ways␈α
to␈α∞look␈α
at␈α∞a␈α
high␈α∞level␈α
language:␈α∞as␈α
a
␈↓ ↓H␈↓mathematical␈α
formalism,␈α∞and␈α
as␈α∞a␈α
programming␈α∞language.␈α
 LISP
␈↓ ↓H␈↓is␈αa␈αbetter␈αformalism␈αthan␈αmost␈αof␈αits␈αmathematical␈αrivals␈αbecause
␈↓ ↓H␈↓there␈αis␈αsufficient␈αorganizational␈αcomplexity␈αpresent␈αin␈αLISP␈αso␈αas
␈↓ ↓H␈↓to␈α∞make␈α∞its␈α∞implementation␈α∞a␈α∞realistic␈α∞computer␈α∞science␈α∞task␈α
and
␈↓ ↓H␈↓not␈α
just␈αan␈α
interesting␈αmathematical␈α
curiosity.␈α Much␈α
of␈αthe␈α
power
␈↓ ↓H␈↓of␈αLISP␈α
lies␈αin␈αits␈α
simplicity.␈α The␈αdata␈α
structures␈αare␈αrich␈α
enough
␈↓ ↓H␈↓to␈α∂easily␈α⊂describe␈α∂sophisticated␈α⊂algorithms␈α∂but␈α∂not␈α⊂so␈α∂rich␈α⊂as␈α∂to
␈↓ ↓H␈↓become␈α
obfuscatory.␈α
 Most␈α
every␈α
aspect␈α
of␈α
the␈α∞implementation␈α
of
␈↓ ↓H␈↓LISP␈α_and␈α↔its␈α_translators␈α↔has␈α_immediate␈α↔implications␈α_to␈α↔the
␈↓ ↓H␈↓implementation␈α≤of␈α≤other␈α≤languages␈α≤and␈α≤to␈α≤the␈α≥design␈α≤of
␈↓ ↓H␈↓programming languages in general.



␈↓ ↓H␈↓We␈αwill␈αdescribe␈α
language␈αtranslators␈α(interpreters␈α
and␈αcompilers)
␈↓ ↓H␈↓as␈α⊗LISP␈α⊗functions.␈α⊗ The␈α⊗structure␈α⊗of␈α⊗these␈α↔translators␈α⊗when
␈↓ ↓H␈↓exposed␈α∞as␈α∞LISP␈α∞functions␈α∞aids␈α∞immensely␈α∞in␈α∞understanding␈α∞the
␈↓ ↓H␈↓essential␈α∞character␈α∞of␈α∞such␈α∞translators.␈α∞ This␈α∞is␈α∞partly␈α∞due␈α∞to␈α
the
␈↓ ↓H␈↓simplicity␈αof␈αthe␈αlanguage,␈αbut␈αperhaps␈αmore␈αdue␈αto␈αour␈αability␈αto
␈↓ ↓H␈↓go␈α∂right␈α∂to␈α∂the␈α∂essential␈α∂translating␈α∂algorithm␈α∂without␈α∞becoming
␈↓ ↓H␈↓bogged down in details of syntax.

␈↓ ↓H␈↓LISP␈α!has␈α!very␈α!important␈α!implications␈α!in␈α!the␈α!field␈α!of
␈↓ ↓H␈↓programming␈α∞language␈α∞semantics,␈α∂and␈α∞is␈α∞the␈α∂dominant␈α∞language
␈↓ ↓H␈↓in␈α_the␈α_closely␈α_related␈α↔study␈α_of␈α_provability␈α_of␈α_properties␈α↔of
␈↓ ↓H␈↓programs.␈α The␈α
idea␈αof␈α
proving␈αproperties␈α
of␈αprograms␈α
has␈αbeen
␈↓ ↓H␈↓around␈α∞for␈α∞a␈α∞very␈α∞long␈α∞time.␈α∞Goldstine␈α∞and␈α∞von␈α∞Neumann␈α
were
␈↓ ↓H␈↓aware␈α∞of␈α∞the␈α∞practical␈α
benefits␈α∞of␈α∞such␈α∞endeavors.␈α∞J.␈α
McCarthy's
␈↓ ↓H␈↓work␈αin␈αLISP␈α
and␈αthe␈αTheory␈α
of␈αComputation␈αsought␈αto␈α
establish
␈↓ ↓H␈↓formalisms␈α∞and␈α
rules␈α∞of␈α∞inference␈α
for␈α∞reasoning␈α∞about␈α
programs.
␈↓ ↓H␈↓However,␈α
the␈α
working␈α
programmers␈α
recognized␈α
debugging␈α
as␈αthe
␈↓ ↓H␈↓only␈α∪tool␈α∩with␈α∪which␈α∩to␈α∪generate␈α∩a␈α∪"correct"␈α∪program,␈α∩though
␈↓ ↓H␈↓clearly␈α
the␈α
non-occurrence␈α
of␈α
bugs␈α
is␈α
no␈α
guarantee␈α
of␈αcorrectness.
␈↓ ↓H␈↓Until␈α⊗very␈α⊗recently␈α⊗techniques␈α⊗for␈α⊗establishing␈α⊗correctness␈α⊗of
␈↓ ↓H␈↓practical programs simply did not exist.

␈↓ ↓H␈↓A recent set of events is beginning to change this.

␈↓ ↓H␈↓␈↓ ↓x␈↓↓1.␈↓␈α⊃Programs␈α⊃are␈α⊂becoming␈α⊃so␈α⊃large␈α⊂and␈α⊃complex␈α⊃that,␈α⊂even
␈↓ ↓H␈↓␈↓ ↓xthough␈α∞we␈α∂write␈α∞in␈α∂a␈α∞high-level␈α∂language,␈α∞our␈α∂intuitions␈α∞are
␈↓ ↓H␈↓␈↓ ↓xnot␈αsufficient␈α
to␈αsustain␈α
us␈αwhen␈αwe␈α
try␈αto␈α
find␈αbugs.␈α
We␈αare
␈↓ ↓H␈↓␈↓ ↓xliterally being forced to look beyond debugging.

␈↓ ↓H␈↓␈↓ ↓x␈↓↓2.␈↓␈α∞The␈α∞formalisms␈α∞are␈α∞maturing.␈α∞We␈α∞know␈α∞a␈α∞lot␈α∞more␈α∞about
␈↓ ↓H␈↓␈↓ ↓xhow␈α∂to␈α∂write␈α∂"structured␈α∞programs";␈α∂we␈α∂know␈α∂how␈α∂to␈α∞design
␈↓ ↓H␈↓␈↓ ↓xlanguages␈α_whose␈α_constructs␈α_are␈α_more␈α_amenable␈α_to␈α↔proof
␈↓ ↓H␈↓␈↓ ↓xtechniques.␈α∀ And␈α∀most␈α∃importantly,␈α∀the␈α∀tools␈α∀we␈α∃need␈α∀for
␈↓ ↓H␈↓␈↓ ↓xexpressing properties of programs are finally being developed.

␈↓ ↓H␈↓␈↓ ↓x␈↓↓3.␈↓␈αThe␈αdevelopment␈αof␈αon-line␈αtechniques.␈αThe␈αon-line␈αsystem,
␈↓ ↓H␈↓␈↓ ↓xwith␈α↔its␈α↔sophisticated␈α↔display␈α↔editors,␈α↔debuggers␈α_and␈α↔file
␈↓ ↓H␈↓␈↓ ↓xhandlers,␈α∪is␈α∪the␈α∪only␈α∪reason␈α∪that␈α∪the␈α∪traditional␈α∪means␈α∩of
␈↓ ↓H␈↓␈↓ ↓xconstruction␈α→and␈α→modification␈α_of␈α→complex␈α→programs␈α_and
␈↓ ↓H␈↓␈↓ ↓xsystems has been able to survive this long.

␈↓ ↓H␈↓This␈αview␈αof␈αthe␈αprogramming␈αprocess␈αblends␈αwell␈αwith␈αthe␈αLISP
␈↓ ↓H␈↓philosophy.␈α⊃ We␈α⊃will␈α⊃show␈α⊃that␈α⊃the␈α⊃most␈α⊃natural␈α⊃way␈α⊃to␈α⊃write



␈↓ ↓H␈↓LISP␈α
programs␈αis␈α
"structured"␈αin␈α
the␈αbest␈α
sense␈αof␈α
the␈αword,␈α
being
␈↓ ↓H␈↓clean␈α⊃in␈α∩control␈α⊃structure,␈α∩concise␈α⊃by␈α⊃not␈α∩attempting␈α⊃to␈α∩do␈α⊃too
␈↓ ↓H␈↓much, and independent of a particular data representation.

␈↓ ↓H␈↓Many␈α↔of␈α↔the␈α↔existing␈α↔techniques␈α↔for␈α↔establishing␈α⊗correctness
␈↓ ↓H␈↓originated␈α∞in␈α∂McCarthy's␈α∞investigations␈α∞of␈α∂LISP;␈α∞and␈α∂some␈α∞very
␈↓ ↓H␈↓recent␈α
work␈α∞on␈α
mathematical␈α∞models␈α
for␈α∞programming␈α
languages
␈↓ ↓H␈↓is easily motivated from a discussion of LISP.

␈↓ ↓H␈↓Finally␈α
there␈α
are␈α
certain␈αproperties␈α
of␈α
LISP-like␈α
languages␈αwhich
␈↓ ↓H␈↓make␈α≠them␈α≤the␈α≠natural␈α≤candidate␈α≠for␈α≤interactive␈α≠program
␈↓ ↓H␈↓specification.␈α∩ In␈α∩the␈α∩chapter␈α∪on␈α∩implications␈α∩of␈α∩LISP␈α∪we␈α∩will
␈↓ ↓H␈↓characterize␈α
"LISP-like"␈α
and␈αshow␈α
how␈α
interactive␈α
methods␈αcan␈α
be
␈↓ ↓H␈↓developed.

␈↓ ↓H␈↓This␈α
text␈αis␈α
primarily␈αdesigned␈α
for␈αundergraduates␈α
and␈αtherefore
␈↓ ↓H␈↓an␈α
attempt␈α
is␈αmade␈α
to␈α
make␈αit␈α
self-contained.␈α
There␈α
are␈αbasically
␈↓ ↓H␈↓five␈α∞areas␈α∞in␈α∞which␈α∞to␈α
partition␈α∞the␈α∞topics:␈α∞the␈α∞mechanics␈α∞of␈α
the
␈↓ ↓H␈↓language,␈α_the␈α_evaluation␈α_of␈α_expressions␈α_in␈α_LISP,␈α_the␈α↔static
␈↓ ↓H␈↓structure␈α↔of␈α⊗LISP,␈α↔the␈α⊗dynamic␈α↔structure␈α⊗of␈α↔LISP,␈α↔and␈α⊗the
␈↓ ↓H␈↓efficient␈α∂representation␈α∂of␈α⊂data␈α∂structures␈α∂and␈α⊂algorithms.␈α∂ Each
␈↓ ↓H␈↓area␈α∀builds␈α∀on␈α∃the␈α∀previous.␈α∀Taken␈α∃as␈α∀a␈α∀group␈α∃these␈α∀topics
␈↓ ↓H␈↓introduce␈αmuch␈αof␈αwhat␈αis␈αinteresting␈αcomputer␈αscience.␈α The␈αfirst
␈↓ ↓H␈↓area␈α∂develops␈α∂the␈α∂programming␈α∂philosophy␈α∂of␈α∂LISP:␈α∂the␈α∂use␈α∞of
␈↓ ↓H␈↓data␈α→structures␈α_in␈α→programming;␈α_the␈α→language␈α→constructs␈α_of
␈↓ ↓H␈↓recursion;␈α⊃and␈α⊃other␈α⊂uncommon␈α⊃control␈α⊃structures.␈α⊃ The␈α⊂second
␈↓ ↓H␈↓area␈α⊃involves␈α⊃a␈α⊃careful␈α⊃study␈α⊂of␈α⊃the␈α⊃meaning␈α⊃of␈α⊃evaluation␈α⊂in
␈↓ ↓H␈↓LISP␈α∀gives␈α∃insights␈α∀into␈α∀other␈α∃languages␈α∀and␈α∀to␈α∃the␈α∀general
␈↓ ↓H␈↓question␈α
of␈αimplementation.␈α
The␈αnext␈α
two␈αareas␈α
are␈αinvolved␈α
with
␈↓ ↓H␈↓implementation.␈α∪The␈α∩section␈α∪on␈α∪static␈α∩structure␈α∪deals␈α∪with␈α∩the
␈↓ ↓H␈↓basic␈α→organization␈α_of␈α→memory␈α_for␈α→a␈α_LISP␈α→machine -- be␈α_it
␈↓ ↓H␈↓hardware␈α↔or␈α↔simulated␈α↔in␈α↔software.␈α↔The␈α↔dynamics␈α_of␈α↔LISP
␈↓ ↓H␈↓discusses␈α&the␈α&primitive␈α%control␈α&structures␈α&necessary␈α%for
␈↓ ↓H␈↓implementation␈α
of␈αthe␈α
LISP␈α
control␈αstructures␈α
and␈αprocedure␈α
calls.
␈↓ ↓H␈↓LISP␈α
compilers␈α∞are␈α
discussed␈α
here.␈α∞ The␈α
final␈α
section␈α∞relates␈α
our
␈↓ ↓H␈↓discussion␈αof␈αLISP␈αand␈αits␈αimplementation␈αto␈αthe␈αmore␈αtraditional
␈↓ ↓H␈↓material␈α∞of␈α∞a␈α∞data␈α∞structures␈α
course.␈α∞We␈α∞discuss␈α∞the␈α∞problems␈α
of
␈↓ ↓H␈↓efficient␈α⊗representation␈α⊗of␈α⊗data␈α⊗structures.␈α⊗By␈α⊗this␈α↔point␈α⊗the
␈↓ ↓H␈↓student␈α∂should␈α∂have␈α∂a␈α∂better␈α∞understanding␈α∂of␈α∂the␈α∂uses␈α∂of␈α∞data
␈↓ ↓H␈↓structures and should be motivated to examine these issues.

␈↓ ↓H␈↓A␈α∞large␈α∞collection␈α∞of␈α∞problems␈α∞has␈α∞been␈α∞included.␈α∞The␈α∞reader␈α∞is
␈↓ ↓H␈↓urged␈α∀to␈α∀do␈α∃as␈α∀many␈α∀as␈α∃possible.␈α∀ The␈α∀problems␈α∃are␈α∀mostly



␈↓ ↓H␈↓non-trivial;␈α∪they␈α∪attempt␈α∪to␈α∩be␈α∪realistic,␈α∪introducing␈α∪some␈α∩new
␈↓ ↓H␈↓information␈α→which␈α→the␈α→readers␈α→should␈α→be␈α→able␈α~to␈α→discover
␈↓ ↓H␈↓themselves.␈α∞There␈α∞are␈α∞also␈α∞a␈α∞few␈α∞rather␈α∞substantial␈α∂projects.␈α∞ At
␈↓ ↓H␈↓least␈α∞one␈α∂should␈α∞be␈α∞attempted.␈α∂ There␈α∞is␈α∞a␈α∂significant␈α∞difference
␈↓ ↓H␈↓between␈αbeing␈αable␈α
to␈αprogram␈αsmall␈α
problems␈αand␈αbeing␈α
able␈αto
␈↓ ↓H␈↓handle large projects.

␈↓ ↓H␈↓The␈αtext␈αis␈αlarge␈αand␈αcovers␈αmuch␈αmore␈αthan␈αis␈αrecommended␈αfor
␈↓ ↓H␈↓a␈α∀one-semester␈α∪course.␈α∀A␈α∪typical␈α∀one␈α∪semester␈α∀course␈α∀on␈α∪data
␈↓ ↓H␈↓structures covers:
␈↓ ↓H␈↓␈↓ αhChapter 1: all
␈↓ ↓H␈↓␈↓ αhChapter 2: without 2.4 and 2.9.
␈↓ ↓H␈↓␈↓ αhChapter 3: without 3.12, and mathematical aspects of 
␈↓ ↓H␈↓␈↓ αhChapter 4: without 4.7, 4.8, and the mathematical asp
␈↓ ↓H␈↓␈↓ αhChapter 5: without 5.8, 5.19, and 5.20
␈↓ ↓H␈↓␈↓ αhChapter 6: without 6.8, 6.9, 6.12 through 6.19
␈↓ ↓H␈↓␈↓ αhChapter 7: without 7.4, 7.5, 7.10 through 7.13
␈↓ ↓H␈↓␈↓ αhChapter 8 is also optional.

␈↓ ↓H␈↓If␈α∞a␈α∞good␈α
interactive␈α∞LISP␈α∞implementation␈α
is␈α∞available,␈α∞then␈α
the
␈↓ ↓H␈↓pace␈α⊂can␈α⊂be␈α⊂quickened␈α⊂and␈α⊂the␈α⊂projects␈α⊂enlarged.␈α⊃ However,␈α⊂if
␈↓ ↓H␈↓only␈α⊃a␈α⊃poor␈α⊃or␈α⊂mediocre␈α⊃implementation␈α⊃is␈α⊃accessible,␈α⊃then␈α⊂the
␈↓ ↓H␈↓course␈αtime␈αis␈α
better␈αspent␈αwithout␈α
␈↓↓any␈↓␈αactual␈αprogramming.␈α
LISP
␈↓ ↓H␈↓is␈α∞an␈α∂interactive␈α∞language;␈α∂attempts␈α∞at␈α∂other␈α∞modes␈α∂of␈α∞operation
␈↓ ↓H␈↓do a disservice to both the language and the user.

␈↓ ↓H␈↓Finally␈α∂a␈α∂note␈α∂on␈α∂the␈α∂structure␈α∂of␈α∂the␈α∂text.␈α∂The␈α∂emphasis␈α∞flows
␈↓ ↓H␈↓from␈α↔the␈α_abstract␈α↔to␈α↔the␈α_specific,␈α↔beginning␈α↔with␈α_a␈α↔precise
␈↓ ↓H␈↓description␈α∞of␈α∞the␈α∞domain␈α∞of␈α∞LISP␈α∞functions␈α∞and␈α∞the␈α∞operations
␈↓ ↓H␈↓defined␈α
over␈α
that␈α
domain,␈α
and␈α
moves␈α
to␈α
a␈α
discussion␈α
of␈αthe␈α
details
␈↓ ↓H␈↓of␈α efficient␈α implementation␈α∨of␈α LISP-like␈α languages.␈α∨ The
␈↓ ↓H␈↓practical-minded␈αprogrammer␈αmight␈αbe␈αput-off␈αby␈αthe␈α"irrelevant"
␈↓ ↓H␈↓theory␈α
and␈α
the␈αtheoretical-minded␈α
mathematician␈α
might␈αbe␈α
put-off
␈↓ ↓H␈↓by␈αthe␈α
"irrelevant"␈αdetails␈α
of␈αimplementation.␈α
If␈αyou␈αlie␈α
somewhere
␈↓ ↓H␈↓between these two extremes, then welcome.



␈↓ ↓H␈↓␈↓ β{BIBLIOGRAPHY




␈↓ ↓H␈↓The basic form of an entry consists of three items:

␈↓ ↓H␈↓␈↓ α_␈↓↓1.␈↓␈α
A␈α
short␈α
name␈α
which␈αis␈α
how␈α
the␈α
document␈α
is␈αreferenced␈α
in
␈↓ ↓H␈↓␈↓ α_the text.

␈↓ ↓H␈↓␈↓ α_␈↓↓2.␈↓ The full bibliographical reference.

␈↓ ↓H␈↓␈↓ α_␈↓↓3.␈↓␈α∪A␈α∩sequence␈α∪of␈α∪pages␈α∩in␈α∪the␈α∪text␈α∩which␈α∪refer␈α∪to␈α∩this
␈↓ ↓H␈↓␈↓ α_document.␈α∞If␈α∞the␈α∂document␈α∞is␈α∞not␈α∞referenced␈α∂the␈α∞statement
␈↓ ↓H␈↓␈↓ α_␈↓↓[ norefs ]␈↓␈α→appears␈α→instead;␈α_these␈α→documents,␈α→while␈α_not
␈↓ ↓H␈↓␈↓ α_referenced, are relevant to the material covered in the text.

␈↓ ↓H␈↓[Weg 70]␈↓ αx1 ␈↓↓[␈↓



␈↓ ↓H␈↓↓␈↓ βαT A B L E   O F   C O N T E N T S



␈↓ ↓H␈↓↓CHAPTER␈↓ πUPAGE␈↓


␈↓ ↓H␈↓␈↓ ↓xBIBLIOGRAPHY␈↓ λ→8



␈↓ ↓H␈↓␈↓ ↓xINDEX␈↓ λ(